In the last decade, centrally hosted network filesystems with disconnected operation have grown to serve hundreds of millions of users. These services include SugarSync®, Dropbox®, Box®, Google Drive®, Microsoft OneDrive®, and Amazon Cloud Drive®.
Commercially, these systems typically offer users a maximum storage quota in exchange for a flat monthly fee, or no fee at all. Meanwhile, the cost to operate such a system increases with the amount of user data actually stored. Therefore, operators benefit from techniques that reduce the net amount of user data stored.
These filesystems can rapidly become gargantuan. For example, one of the above-mentioned services currently stores roughly one Exabyte of user data of which roughly 40% is made of baseline compressed JPEG images.
Baseline Joint Photographic Experts Group (JPEG) image compression encompasses a lossy encoding process based on a discrete cosine transform (DCT). In the encoding process, source image data is grouped into 8 by 8 blocks of samples. Each sample block is transformed by a forward DCT into a set of 64 values referred to as DCT coefficients. Of the 64 values, one of the values is referred to as the DC coefficient and the other 63 values as the AC coefficients. Each of the 64 coefficients are quantized using one of 64 corresponding values from a quantization table.
After quantization, the quantized DC coefficient and the 63 quantized AC coefficients are entropy encoded. In doing so, the previous quantized DC coefficient is used to predict the current quantized DC coefficient, and the difference is encoded. The 63 quantized AC coefficients are converted into a zig zag sequence. The quantized DCT coefficients are then passed to a Huffman encoding procedure which compresses the data further.
For decoding the compressed JPEG image data, essentially the inverse of the encoding steps is performed. The entropy decoder decodes the zig zag sequence of quantized DCT coefficients. After dequantization, the DCT coefficients are transformed to an 8×8 block of samples by an inverse DCT (IDCT).
Large-scale centrally hosted network filesystems such as those mentioned above would appreciate techniques providing greater compression efficiency relative to baseline JPEG. Such techniques could be employed to reduce the total size of the user data corpus stored and thereby reduce operating costs.
Methods exist for improved image compression relative to baseline JPEG. In one approach named “packJPG,” segmented entropy encoding is employed in reference to the End-of-Block (EOB) of the 8 by 8 DCT transformed block. The EOB is defined as the position after the last non-zero coefficient in the zig-zag order of the 64 coefficients. The packJPG approach purportedly can reduce baseline JPEG image file sizes by an average of 15%. More information on packJPG is available in the paper by Stirner M. and Seelmann G., “Improved Redundancy Reduction for JPEG Files,” Picture Coding Symposium by ERASIP, November 2007.
While the packJPG approach can recompress a baseline JPEG file with a reduced file size, the packJPG approach requires re-arranging compressed pixel values in a globally sorted order. As a result, decompressing a packJPG compressed image to the original baseline JPEG image may be single-threaded, may require access to the entire packJPG compressed image, and may require decoding the packJPG compressed image into memory before a first byte of the original baseline JPEG compressed image can be output. Overall, the time-to-first byte and the time-to-last byte for the decompression operation may be too high to meet the service goals of large-scale centrally hosted network filesystems such as those mentioned above.
What is needed, then, are image recompression techniques that can be implemented without global operations so that the decompression operation to recover the original compressed image from the recompressed image can be distributed across independent portions of the recompressed image and, within each portion, multithreaded and with low time-to-first byte.